\section{8. Patterns 5: Redegør for følgende concurrency mønstre }

\begin{center}
\line(1,0){500}
\end{center}

\begin{itemize}
\item Parrallel Loops
\item Passing data
\item Producer/consumer 
\item Mapreduce 
\item Shared state 
\end{itemize}
\begin{center}
\line(1,0){500}
\end{center}

\subsubsection{Parrallel Loops}
\begin{itemize}
    \item \textbf{Parallel For Loop}
    \begin{itemize}
        \item Kan implementeres med statisk eller dynamisk partitionering
        \item Statisk giver mindre synkronisering og mindre load-balancing
        \item Dynamisk giver mere load-balancing og overhead
        \begin{lstlisting}
void MyParallelFor(int LowerBound, int UpperBound, Action<int> body);
        \end{lstlisting}
        \item Parallel.For findes i .NET
        \begin{lstlisting}
public static ParallelLoopResult For(
int fromInclusive, int toExclusive, Action<int> body);
        \end{lstlisting}
        \item Benytter ThreadPool i så mange tråde som muligt
        \item Forsøger at maksimere effektivitet mens overhead minimeres
        \item Exception handling, Break, int32-64 ranges, Thread-local state
        \item Nested parallelism - Parallel.For nested i hinanden deler ressourcer 
    \end{itemize}
    \begin{center}
    \textbf{Parallel Foreach example}
    \includegraphics[scale=0.8]{8-parallelforeach}    
    \end{center}
    \item \textbf{Parallel ForAll}
    \begin{lstlisting}
List<InputData> inputData = ...; 
inputData.AsParallel().Select(i => new OutputData(i)).ForAll(o => 
{ 
  ProcessOutput(o); 
});
    \end{lstlisting}
\end{itemize}
\subsubsection{Passing data}
\begin{itemize}
    \item State Objects
    \begin{itemize}
        \item Passing data igennem state uden for en thread delegate
        \begin{lstlisting}
Task.Factory.StartNew(()=> { 
	Console.WriteLine(externaldata); });
        \end{lstlisting}
    \end{itemize}
    \item \textbf{State Objects}
    \begin{lstlisting}
class Work { 
  public int data; 
  public void Run() { Console.WriteLine(data); }} 
// ... 
Work w = new Work(); 
w.Data = 42;
Task.Factory.StartNew(w.Run);
    \end{lstlisting}    
    \item MQ+mediator, shared memory etc
\end{itemize}
\subsubsection{Producer/Consumer}
\begin{itemize}
    \item System.Collections.Concurrent.BlockingCollection<T>
    \begin{itemize}
        \item BoundedCapacity
        \item Blokkerer producer hvis collectionen er "fuld" - produceren sløves
    \end{itemize}
    \item Parallelize Processing
    \begin{lstlisting}
foreach(var line in inputLines.GetConsumingEnumerable() 
	.AsParallel().AsOrdered() 
	.Select(line => Regex.Replace(line, @"\s+", ", "))) 
    \end{lstlisting}
    \begin{itemize}
        \item .AsOrdered sørger for at PLINQ beholder den samme orden som den sekventielle løsning
    \end{itemize}
\end{itemize}
\subsubsection{MapReduce}
\begin{itemize}
    \item MapReduce i PLINQ
\begin{lstlisting}
public static ParallelQuery<TResult> MapReduce<TSource, TMapped, 
                                               TKey, TResult>( 
this ParallelQuery<TSource> source, 
Func<TSource, IEnumerable<TMapped>> map, 
Func<TMapped, TKey> keySelector, 
Func<IGrouping<TKey, TMapped>, IEnumerable<TResult>> reduce) 
{ 
   return source. 
          SelectMany(map). 
          GroupBy(keySelector). 
          SelectMany(reduce); 
}
\end{lstlisting}
\item \textbf{Typisk Eksempel:  Word counting}
\begin{itemize}
    \item Map phase: input: document, output: all words in document
    \item Grouping phase: identical words grouped together
    \item Redude phase: input: word groups, output: count/word pair    
\end{itemize}
\end{itemize}
\subsubsection{Shared state}
\begin{itemize}
    \item Delete ressourcer 
    \begin{itemize}
        \item Synchronization - locks etc
        \item Immutability - ikke noget problem
        \item Isolation - ingen delte data
    \end{itemize}
    \item TLS - Thread-Local State
    \begin{lstlisting}
[ThreadStatic] 
static Random _rand; 
 
static int GetRandomNumber() 
{ 
  if (_rand == null) _rand = new Random(); 
  return _rand.Next(); 
}
    \end{lstlisting}
    \begin{itemize}
    	\item + Hurtigste local-storage  
    	\item - Virker ikke på instans medlemmer  
    \end{itemize}    
    \item AllocateDataSlot
    \begin{lstlisting}
public class MyType { 
	private LocalDataStoreSlot _rand = Thread.AllocateDataSlot();  
 	public int GetRandomNumber() { 
  		Random r = (Random)Thread.GetData(_rand); 
    	if (r == null) { 
     		r = new Random(); 
      		Thread.SetData(_rand, r); 
		} 
	return r.Next(); 
  	} 
}
    \end{lstlisting}
    \begin{itemize}
        \item + Per-Thread Per-Instance
        \item - "Object" bruges, der skal typecastes
        \item - Langsom, "boxing"
    \end{itemize}
    \item ThreadLocal fra .NET 4
    \begin{lstlisting}
public class MyType { 
	//Delegate initializer run on each thread 
	private ThreadLocal<Random> _rand = 
		new ThreadLocal<Random>(() => new Random()); 
	public int GetRandomNumber() { return _rand.Value.Next(); } 
}
    \end{lstlisting}
    \begin{itemize}
        \item + Generisk, ingen typecast eller boxing
        \item + Kan blive initialiseret på alle tråde der tilgår den
        \item + Hurtig, men langsommere end ThreadStatic
        \item - Bruger meget hukommelse
    \end{itemize}
    
    \item \textbf{Generelt}
    \begin{itemize}
        \item Det er langsommere at tilgå TLS end en local kopi
    \end{itemize}
\end{itemize}